Connected greedy coloring of H-free graphs

DOI10.1016/J.DAM.2020.04.024MaRDI QIDQ777440zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 7 July 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.09034

zbMATH Keywords

computational complexitygreedy coloringvertex coloring\(H\)-free graphsconnected greedy coloring

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Abstract: A connected ordering $(v_1,v_2,ldots,v_n)$ of $V(G)$ is an ordering of the vertices such that $v_i$ has at least one neighbour in $v_1,ldots,v_{i-1}$ for every $iin2,ldots,n$. A connected greedy coloring (CGC for short) is a coloring obtained by applying the greedy algorithm to a connected ordering. This has been first introduced in 1989 by Hertz and de Werra, but still very little is known about this problem. An interesting aspect is that, contrary to the traditional greedy coloring, it is not always true that a graph has a connected ordering that produces an optimal coloring; this motivates the definition of the connected chromatic number of $G$, which is the smallest value $ch{i}_c(G)$ such that there exists a CGC of $G$ with $ch{i}_c(G)$ colors. An even more interesting fact is that $ch{i}_c(G)lechi(G)+1$ for every graph $G$ (Benevides et. al. 2014). In this paper, in the light of the dichotomy for the coloring problem restricted to $H$-free graphs given by Kr'al et.al. in 2001, we are interested in investigating the problems of, given an $H$-free graph $G$: (1). deciding whether $ch{i}_c(G)=chi(G)$; and (2). given also a positive integer $k$, deciding whether $ch{i}_c(G)lek$. We have proved that Problem (2) has the same dichotomy as the coloring problem (i.e., it is polynomial when $H$ is an induced subgraph of $P_4$ or of $P_3+K_1$, and it is NP-complete otherwise). As for Problem (1), we have proved that $ch{i}_c(G)=chi(G)$ always hold when $G$ is an induced subgraph of $P_5$ or of $P_4+K_1$, and that it is NP-hard to decide whether $ch{i}_c(G)=chi(G)$ when $H$ is not a linear forest or contains an induced $P_9$. We mention that some of the results actually involve fixed $k$ and fixed $chi(G)$.

Recommendations

• Connected greedy colourings
• A note on connected greedy edge colouring
• 4-coloring \(H\)-free graphs when \(H\) is small
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small

Cites work

• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• An introduction to timetabling
• Characterizations of derived graphs
• Coloring edges and vertices of graphs without short or long cycles
• Connected greedy colourings
• Connected sequential colourings
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Dominating cliques in \(P_ 5\)-free graphs
• Every planar map is four colorable. II: Reducibility
• Four-coloring \(P_6\)-free graphs
• Hard-to-color graphs for connected sequential colorings
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• New methods to color the vertices of a graph
• Parallel iterative methods for sparse linear systems
• Some perfect coloring properties of graphs
• Some simplified NP-complete graph problems
• Sur le coloriage des graphs
• The NP-Completeness of Edge-Coloring
• \(H\)-colouring \(P_t\)-free graphs in subexponential time

Cited in

(7)

• Obtaining the Grundy chromatic number: how bad can my greedy heuristic coloring be?
• A note on connected greedy edge colouring
• Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
• The connected Grundy coloring problem: formulations and a local-search enhanced biased random-key genetic algorithm
• Connected sequential colourings
• Connected greedy colourings
• Making an H H‐free graph k k‐colorable

This page was built for publication: Connected greedy coloring of \(H\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777440)