On minimal triangle-free planar graphs with prescribed 1-defective chromatic number

2015/01/19 by Nirmala Achuthan, Achuthan, Nirmala, N. R. Achuthan +3
Computer Science · Mathematics · #05C15 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1501.04387

openalex publication_date 2015/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph is (m,k)-colourable if its vertices can be coloured with m colours such that the maximum degree of the subgraph induced on the set of all vertices receiving the same colour is at most k. The k-defective chromatic number χ_k(G) is the least positive integer m for which graph G is (m,k)-colourable. Let f(m,k;tfp) be the smallest order of a triangle-free planar graph such that χ_k(G)=m. In this paper we show that f(3,1;tfp)=11.

Related

• On triangle-free graphs of order 10 with prescribed 1-defective chromatic number
• Defective and Clustered Colouring of Graphs with Given Girth
• Multiple list colouring triangle-free planar graphs
• Chromatic number and mimimum degree of K_r-free graphs
• Vertex partitions of (C₃,C₄,C₆)-free planar graphs