Results 41 to 50 of about 4,003 (201)
A Note on Edge‐Group Choosability of Planar Graphs without 5‐Cycles
Journal of Mathematics, Volume 2020, Issue 1, 2020., 2020 This paper is devoted to a study of the concept of edge‐group choosability of graphs. We say that G is edge‐k‐group choosable if its line graph is k‐group choosable. In this paper, we study an edge‐group choosability version of Vizing conjecture for planar graphs without 5‐cycles and for planar graphs without noninduced 5‐cycles (2010 Mathematics ...
Amir Khamseh, Andrei V. Kelarev
wiley +1 more source
Nullspace Embeddings for Outerplanar Graphs [PDF]
, 2017 21 pages.
Lovász, L., Schrijver, A.
openaire +5 more sources
Nonplanarity of Iterated Line Graphs
Journal of Mathematics, Volume 2020, Issue 1, 2020., 2020 The 1‐crossing index of a graph G is the smallest integer k such that the kth iterated line graph of G has crossing number greater than 1. In this paper, we show that the 1‐crossing index of a graph is either infinite or it is at most 5. Moreover, we give a full characterization of all graphs with respect to their 1‐crossing index.
Jing Wang, Alfred Peris
wiley +1 more source
Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract [PDF]
Discrete Mathematics & Theoretical Computer Science, 2015 We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_ ...
Konstantinos Panagiotou +2 more
doaj +1 more source
On Another Class of Strongly Perfect Graphs
Mathematics, 2022 For a commutative ring R with unity, the associate ring graph, denoted by AG(R), is a simple graph with vertices as nonzero elements of R and two distinct vertices are adjacent if they are associates.
Neha Kansal +3 more
doaj +1 more source
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs [PDF]
, 2008 We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as described in (Mulmuley et al.
Datta, Samir +2 more
core +7 more sources
Adjacency posets of outerplanar graphs [PDF]
Discrete Mathematics, 2021 Felsner, Li and Trotter showed that the dimension of the adjacency poset of an outerplanar graph is at most 5, and gave an example of an outerplanar graph whose adjacency poset has dimension 4. We improve their upper bound to 4, which is then best possible.
openaire +3 more sources
Game Chromatic Number of Generalized Petersen Graphs and Jahangir Graphs
Journal of Applied Mathematics, Volume 2020, Issue 1, 2020., 2020 Let G = (V, E) be a graph, and two players Alice and Bob alternate turns coloring the vertices of the graph G a proper coloring where no two adjacent vertices are signed with the same color. Alice′s goal is to color the set of vertices using the minimum number of colors, which is called game chromatic number and is denoted by χg(G), while Bob′s goal is
Ramy Shaheen +3 more
wiley +1 more source
Algorithms, 2013 The maximum common connected edge subgraph problem is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs, where it has applications in pattern recognition and chemistry.
Takeyuki Tamura, Tatsuya Akutsu
doaj +1 more source
On Supergraphs Satisfying CMSO Properties [PDF]
Logical Methods in Computer Science, 2021 Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function $f$, there is an algorithm $\mathfrak{A}$ that takes as input a CMSO sentence $\varphi$, a positive integer $t$, and a ...
Mateus de Oliveira Oliveira
doaj +1 more source