On 3-Coloring of (2P4,C5)-Free Graphs Jelínek, Vít; Klimošová, Tereza; Masařík, Tomáš ...
Algorithmica,
2022/6, Volume:
84, Issue:
6
Journal Article
Peer reviewed
Open access
The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden ...induced subgraphs
H
1
,
H
2
,
…
; the graphs in the class are called
(
H
1
,
H
2
,
…
)
-free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs. For
H
-free graphs, the complexity is settled for any
H
on up to seven vertices. There are only two unsolved cases on eight vertices, namely
2
P
4
and
P
8
. For
P
8
-free graphs, some partial results are known, but to the best of our knowledge,
2
P
4
-free graphs have not been explored yet. In this paper, we show that the 3-coloring problem is polynomial-time solvable on
(
2
P
4
,
C
5
)
-free graphs.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
The aim of graph clustering is to partition the given graph into subgraphs, and then assign the subgraphs to overlapping or non-overlapping clusters. In this process, densely connected subgraphs fall ...into a single cluster, thereby maximizing the intra-cluster similarity. Here we propose a clustering method based on the shortest path between the nodes. We propose a 2- partition in a few graph classes namely outerplanar graphs, graphs with simplicial vertices, chordal graphs, distance hereditary graphs and cographs. The solution to the chordal and outerplanar graphs can be found in linear time. Chordal graphs are widely used in perfect phylogeny related research whereas cographs are used to model the orthology relations. Hence a clustering method based on shortest path in chordal graphs and cographs may have significant impact in the research related to orthologous genes as well as phylogenetic relations.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
On the chromatic index of cographs and join graphs Cunha Lima, Alex R.; Garcia, Georgia; Zatesko, Leandro M. ...
Electronic notes in discrete mathematics,
December 2015, 2015-12-00, Volume:
50
Journal Article
Along with a result of Niessen of 1994, a conjecture proposed by Hilton and Chetwynd of 1986 implies that the chromatic index of graphs with Δ≥n/2 can be determined in linear time. Connected cographs ...satisfy Δ≥n/2, however whether the conjecture holds for cographs is still unknown. This paper presents sufficient conditions for cographs and join graphs to be Class 1.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
34.
Induced betweenness in order-theoretic trees Courcelle, Bruno
Discrete mathematics and theoretical computer science,
09/2022, Volume:
23 no. 2, special issue..., Issue:
Special issues
Journal Article
Peer reviewed
Open access
The ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure. In a partially ordered set (N,≤), ...B(x,y,z):⇔x<y<z∨z<y<x, and the corresponding betweenness structure is (N,B). The class of betweenness structures of linear orders is first-order definable. That of partial orders is monadic second-order definable. An order-theoretic tree is a partial order such that the set of elements larger that any element is linearly ordered and any two elements have an upper-bound. Finite or infinite rooted trees ordered by the ancestor relation are order-theoretic trees. In an order-theoretic tree, B(x,y,z) means that x<y<z or z<y<x or x<y≤x⊔z or z<y≤x⊔z, where x⊔z is the least upper-bound of incomparable elements x and z. In a previous article, we established that the corresponding class of betweenness structures is monadic second-order definable.We prove here that the induced substructures of the betweenness structures of the countable order-theoretic trees form a monadic second-order definable class, denoted by IBO. The proof uses a variant of cographs, the partitioned probe cographs, and their known six finite minimal excluded induced subgraphs called the bounds of the class. This proof links two apparently unrelated topics: cographs and order-theoretic trees.However, the class IBO has finitely many bounds, i.e., minimal excluded finite induced substructures. Hence it is first-order definable. The proof of finiteness uses well-quasi-orders and does not provide the finite list of bounds. Hence, the associated first-order defining sentence is not known.
Full text
Available for:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
An acyclic coloring of a graph G is a proper vertex coloring such that G contains no bicolored cycles. The more restricted notion of star coloring of G is an acyclic coloring in which each path of ...length 3 is not bicolored. In this paper, we mainly study on the acyclic and star coloring of P4-reducible and P4-sparse graphs. Moreover, we list polynomial-time algorithms for giving an optimal acyclic or star coloring of a P4-reducible or P4-sparse graph.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
Given a simple graph
G
, a set
C
⊆
V
(
G
)
is a neighborhood cover set if every edge and vertex of
G
belongs to some
G
v
with
v
∈
C
, where
G
v
denotes the subgraph of
G
induced by the closed ...neighborhood of the vertex
v
. Two elements of
E
(
G
)
∪
V
(
G
)
are neighborhood-independent if there is no vertex
v
∈
V
(
G
)
such that both elements are in
G
v
. A set
S
⊆
V
(
G
)
∪
E
(
G
)
is neighborhood-independent if every pair of elements of
S
is neighborhood-independent. Let
ρ
n
(
G
)
be the size of a minimum neighborhood cover set and
α
n
(
G
)
of a maximum neighborhood-independent set. Lehel and Tuza defined neighborhood-perfect graphs
G
as those where the equality
ρ
n
(
G
′
)
=
α
n
(
G
′
)
holds for every induced subgraph
G
′
of
G
. In this work we prove forbidden induced subgraph characterizations of the class of neighborhood-perfect graphs, restricted to two superclasses of cographs:
P
4
-tidy graphs and tree-cographs. We give as well linear-time algorithms for solving the recognition problem of neighborhood-perfect graphs and the problem of finding a minimum neighborhood cover set and a maximum neighborhood-independent set in these same classes. Finally we prove that although for complements of trees finding these optimal sets can be achieved in linear-time, for complements of bipartite graphs it is
NP
-hard.
Confining the robber on cographs Masjoody, Masood
Contributions to discrete mathematics,
01/2023, Volume:
18, Issue:
1
Journal Article
Peer reviewed
Open access
In a game of Cops and Robbers on graphs, usually the cops' objective is to capture the robber---a situation which the robber wants to avoid invariably. In this paper, we begin with introducing the ...notions of trapping and confining the robber and discussing their relations with capturing the robber. Our goal is to study the confinement of the robber on graphs that are free of a fixed path as an induced subgraph. We present some necessary conditions for graphs $G$ not containing the path on $k$ vertices (referred to as $P_k$-free graphs) for some $k\ge 4$, so that $k-3$ cops do not have a strategy to capture or confine the robber on $G$ (Propositions 2.1, 2.3). We then show that for planar cographs and planar $P_5$-free graphs the confining cop number is at most one and two, respectively (Corollary 2.4). We also show that the number of vertices of a connected cograph on which one cop does not have a strategy to confine the robber has a tight lower bound of eight. Moreover, we explore the effects of twin operations---which are well known to provide a characterization of cographs---on the number of cops required to capture or confine the robber on cographs. Finally, we pose two conjectures on confining the robber on $P_5$-free graphs and the smallest planar graph of confining cop number of three.
A
connection tree
of a graph
G
for a
terminal set W
is a tree subgraph
T
of
G
such that leaves(
T
) ⊆
W
⊆
V(T)
. A non-terminal vertex is called
linker
if its degree in
T
is exactly 2, and it is ...called
router
if its degree in
T
is at least 3. The T
erminal connection
problem (TCP) asks whether
G
admits a connection tree for
W
with at most ℓ linkers and at most
r
routers, while the S
teiner tree
problem asks whether
G
admits a connection tree for
W
with at most
k
non-terminal vertices. We prove that, if
r
≥ 1 is fixed, then TCP is polynomial-time solvable when restricted to split graphs. This result separates the complexity of TCP from the complexity of S
teiner tree
, which is known to be NP-complete on split graphs. Additionally, we prove that TCP is NP-complete on strongly chordal graphs, even if
r
≥ 0 is fixed, whereas S
teiner tree
is known to be polynomial-time solvable. We also prove that, when parameterized by clique-width, TCP is W1-hard, whereas S
Teiner tree
is known to be in FPT. On the other hand, agreeing with the complexity of S
teiner tree
, we prove that TCP is linear-time solvable when restricted to cographs (
i.e.
graphs of clique-width 2). Finally, we prove that, even if either ℓ ≥ 0 or
r
≥ 0 is fixed, TCP remains NP-complete on graphs of maximum degree 3.
A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer ...χb(G) for which G has a b-coloring with χb(G) colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval χ(G),χb(G). It is known that not all graphs are b-continuous, and also that the cartesian product and the strong product do not preserve b-continuity. However, the same is not known to be true about the lexicographic product GH. Here, we prove that GH is b-continuous whenever H is b-continuous and G is an interval graph, a block graph or a cograph.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
PDF
