Connected greedy coloring of H-free graphs

DOI10.1016/J.DAM.2020.04.024zbMATH Open1443.05073arXiv1807.09034OpenAlexW3025659069MaRDI QIDQ777440FDOQ777440

Authors: D. Kharzeev 

Publication date: 7 July 2020

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

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)$.

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

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

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)

Cites Work

• Parallel iterative methods for sparse linear systems
• Sur le coloriage des graphs
• Some perfect coloring properties of graphs
• Every planar map is four colorable. II: Reducibility
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Linear degree extractors and the inapproximability of max clique and chromatic number
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Characterizations of derived graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Some simplified NP-complete graph problems
• Dominating cliques in \(P_ 5\)-free graphs
• New methods to color the vertices of a graph
• An introduction to timetabling
• Coloring edges and vertices of graphs without short or long cycles
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Connected sequential colourings
• Hard-to-color graphs for connected sequential colorings
• Complexity of Grundy coloring and its variants
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Four-coloring P₆-free graphs
• Connected Greedy Colourings

Cited In (4)

• A note on connected greedy edge colouring
• Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
• Connected sequential 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)