TITLE

# Chromatic Number of ISK4-Free Graphs

AUTHOR(S)
Le, Ngoc
PUB. DATE
November 2017
SOURCE
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1635
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
A graph G is said to be ISK4-free if it does not contain any subdivision of \$\$K_4\$\$ as an induced subgraph. In this paper, we propose new upper bounds for the chromatic number of ISK4-free graphs and \$\$\{\$\$ ISK4, triangle \$\$\}\$\$ -free graphs.
ACCESSION #
126308045

## Related Articles

• Further Properties of Trees with Minimal Atom-Bond Connectivity Index. Jianping Liu; Jinsong Chen // Abstract & Applied Analysis;2014, p1

Let G = (V, E) be a graph the atom-bond connectivity (ABC) index is defined as the sum of weights ((du + dv - 2 ) /dudv)1/2 over all edges uv of G, where du denotes the degree of a vertex u of G. In this paper, we determined a few structural features of the trees with minimal ABC index also we...

• Independent Monopoly Size In Graphs. Naji, Ahmed Mohammed; Soner, N. D. // Applications & Applied Mathematics;Dec2015, Vol. 10 Issue 2, p738

In a graph G = (V;E), a set D âŠ† V (G) is said to be a monopoly set of G if every vertex v 2 V âˆŠD has at least d(v)/2 neighbors in D. The monopoly size of G, denoted mo(G), is the minimum cardinality of a monopoly set among all monopoly sets in G. The set D âŠ† V (G) is an...

• Neighborhood Total 2-Domination in Graphs. Sivagnanam, C. // International Journal of Mathematical Combinatorics;Dec2014, Vol. 4, p108

Let G = (V,E) be a graph without isolated vertices. A set S âŠ† V is called the neighborhood total 2-dominating set (nt2d-set) of a graph G if every vertex in V âˆ’ S is adjacent to at least two vertices in S and the induced subgraph < N(S) > has no isolated vertices. The minimum...

• Some Minimal (r, 2, k)-Regular Graphs Containing a Given Graph and its Complement. Maheswari, N. R. Santhi; Sekar, C. // International Journal of Mathematical Combinatorics;Mar2015, Vol. 1, p65

A graph G is called (r, 2, k)-regular graph if each vertex of G is at a distance 1 away from r vertices of G and each vertex of G is at a distance 2 away from k vertices of G [9]. This paper suggest a method to construct a ((m+2(nâˆ’1)), 2, (mâˆ’1)(2nâˆ’1)))-regular graph H4 of...

• On 3-Regular Bipancyclic Subgraphs of Hypercubes. Borse, Y. M.; Shaikh, S. R. // International Journal of Combinatorics;5/5/2015, Vol. 2015, p1

The n-dimensional hypercube Qn is bipancyclic; that is, it contains a cycle of every even length from 4 to 2n. In this paper, we prove that Qnâ€‰â€‰(nâ‰¥3) contains a 3-regular, 3-connected, bipancyclic subgraph with l vertices for every even l from 8 to 2n except 10.

• Semitotal Domination in Claw-Free Cubic Graphs. Henning, Michael; Marcon, Alister // Annals of Combinatorics;Dec2016, Vol. 20 Issue 4, p799

In this paper, we continue the study of semitotal domination in graphs in [Discrete Math. 324, 13-18 (2014)]. A set \$\${S}\$\$ of vertices in \$\${G}\$\$ is a semitotal dominating set of \$\${G}\$\$ if it is a dominating set of \$\${G}\$\$ and every vertex in \$\${S}\$\$ is within distance 2 of another vertex of...

• GRAPHS COSPECTRAL WITH A FRIENDSHIP GRAPH OR ITS COMPLEMENT. ABDOLLAHI, A.; JANBAZ, S.; OBOUDI, M. R. // Transactions on Combinatorics;2013, Vol. 2 Issue 4, p37

Let n be any positive integer and Fn be the friendship (or Dutch windmill) graph with 2n+1 vertices and 3n edges. Here we study graphs with the same adjacency spectrum as Fn. Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same. Let G be a graph...

• A note on neighborhood total domination in graphs. RAD, NADER JAFARI // Proceedings of the Indian Academy of Sciences: Mathematical Scie;Aug2015, Vol. 125 Issue 3, p271

Let G = (V,E) be a graph without isolated vertices. A dominating set S of G is called a neighborhood total dominating set (or just NTDS) if the induced subgraph G[N(S)] has no isolated vertex. The minimum cardinality of a NTDS of G is called the neighborhood total domination number of G and is...

• On Zero-Sum and Almost Zero-Sum Subgraphs Over \$\${\mathbb {Z}}\$\$. Caro, Yair; Yuster, Raphael // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p49

For a graph \$\$H\$\$ with at most \$\$n\$\$ vertices and a weighing of the edges of \$\$K_n\$\$ with integers, we seek a copy of \$\$H\$\$ in \$\$K_n\$\$ whose weight is minimal, possibly even zero. Of a particular interest are the cases where \$\$H\$\$ is a spanning subgraph (or an almost spanning subgraph) and the...

• Around The Berge Problem And Hadwiger Conjecture. Nemron, Ikorong Anouk Gilbert // International Journal of Mathematical Combinatorics;Jul2012, Vol. 3, p72

We say that a graph B is berge, if every graph B' âˆˆ {B,BÌ„} does not contain an induced cycle of odd length â‰¥ 5 [BÌ„ is the complementary graph of B]. A graph G is perfect if every induced subgraph G' of G satisfies Ï‡(G ) = Ï‰(G ), where Ï‡(G') is the chromatic number...

Share