Hard-to-color graphs for connected sequential colorings
type: Item
instance of: scholarly article
title: Hard-to-color graphs for connected sequential colorings
zbMATH Open document ID: 0805.05026
DOI: 10.1016/0166-218X(94)90090-6
author: Luitpold Babel
author: Gottfried Tinhofer
published in: Discrete Applied Mathematics
publication date: 1995-01-26T00:00:00Z
review text: A graph \(G\) is said to be hard-to-colour if any connected colouring produces a nonoptimal colouring, and partially hard-to-colour if any such colouring starting in a specified vertex is nonoptimal. The authors show that the linked pair of twin kites with 18 vertices is the smallest cubic hard-to-colour graph and they conjecture that this graph is the smallest graph hard-to-colour from any starting point.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 612426
zbMATH Keywords: connected colouring
zbMATH Keywords: hard-to-colour graph
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
cites work: New methods to color the vertices of a graph
cites work: Q3347930
cites work: The smallest hard-to-color graph
cites work: Parallel concepts in graph theory
cites work: Connected sequential colourings
cites work: Q5670645
cites work: Q5752591
full work available at URL: 0166-218x(94)90090-6
OpenAlex ID: W2023692548
Recommended article: Q4529311
Recommended article: Q2712308
Recommended article: Some sequential graph colouring algorithms
Recommended article: Consecutive colorings of graphs
Recommended article: Sequential colorings and perfect graphs
Recommended article: Connected sequential colourings
Recommended article: Q4936660
Recommended article: Hardness results for three kinds of colored connections of graphs
Recommended article: Coloring Graphs with Constraints on Connectivity
Recommended article: Q3166001
description: scientific article; zbMATH DE number 612426