Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
The Alon-Tarsi number of planar graphs without some forbidden configurations
View through CrossRef
The Alon-Tarsi number of a graph G AT(G) defined as the smallest integer k admitting an Alon-Tarsi orientation with maximum out-degree at most k-1, satisfies the fundamental inequalities χl(G)≤AT(G)≤d(G)+1, where χl(G) and d(G) denote the list chromatic number and degeneracy respectively. Notably, for planar graphs without k-cycles where k∈{5,6}, the 3-degeneracy implies AT(G)≤4, and our main result extends this by proving AT(G)≤ 4 for planar graphs without 4-cycles adjacent to 3-cycles, thereby improving previous results from [JCTB 1999] and [Discrete Math. 2016].
Title: The Alon-Tarsi number of planar graphs without some forbidden configurations
Description:
The Alon-Tarsi number of a graph G AT(G) defined as the smallest integer k admitting an Alon-Tarsi orientation with maximum out-degree at most k-1, satisfies the fundamental inequalities χl(G)≤AT(G)≤d(G)+1, where χl(G) and d(G) denote the list chromatic number and degeneracy respectively.
Notably, for planar graphs without k-cycles where k∈{5,6}, the 3-degeneracy implies AT(G)≤4, and our main result extends this by proving AT(G)≤ 4 for planar graphs without 4-cycles adjacent to 3-cycles, thereby improving previous results from [JCTB 1999] and [Discrete Math.
2016].
Related Results
A Note on Alon–Tarsi Shortest Cycle Cover Conjecture
A Note on Alon–Tarsi Shortest Cycle Cover Conjecture
ABSTRACT
The shortest cycle cover conjecture (SCC conjecture), proposed by Alon and Tarsi, asserts that every bridgeless cubic graph has a cycle cover with a tot...
On the reciprocal distance spectrum of edge corona of graphs
On the reciprocal distance spectrum of edge corona of graphs
The reciprocal distance spectrum (Harary spectrum) of a connected graph [Formula: see text] is the multiset of eigenvalues of its reciprocal distance matrix (Harary matrix) [Formul...
Data Analytics on Graphs Part I: Graphs and Spectra on Graphs
Data Analytics on Graphs Part I: Graphs and Spectra on Graphs
The area of Data Analytics on graphs promises a paradigm shift, as we approach information processing of new classes of data which are typically acquired on irregular but structure...
Computing the Energy of Certain Graphs based on Vertex Status
Computing the Energy of Certain Graphs based on Vertex Status
Background:
The concept of Hückel molecular orbital theory is used to compute the graph energy numerically and graphically on the base of the status of a vertex.
Objective:
Our a...
Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below
Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below
Abstract
The smallest eigenvalue of a graph is the smallest eigenvalue of its adjacency matrix. We show that the family of graphs with smallest eigenvalue at least
...
Indeterminate solitary vertebral lesions on planar scintigraphy
Indeterminate solitary vertebral lesions on planar scintigraphy
Summary
Objective: This study aims to evaluate the added value of hybrid SPECT-CT in differential diagnosis of indeterminate solitary vertebral lesion (SVL) on planar sci...
Planarity testing of doubly periodic infinite graphs
Planarity testing of doubly periodic infinite graphs
AbstractThis paper describes an efficient way to test the VAP‐free (Vertex Accumulation Point free) planarity of one‐ and two‐dimensional dynamic graphs. Dynamic graphs are infinit...
Eigenspectral Analysis of Pendant Vertex- and Pendant Edge-Weighted Graphs of Linear Chains, Cycles, and Stars
Eigenspectral Analysis of Pendant Vertex- and Pendant Edge-Weighted Graphs of Linear Chains, Cycles, and Stars
Abstract
Three classes of pendent vertex- and pendant edge-weighted graphs of linear chains (class I), stars (class II), and cycles (class III) have been presented. ...